#include <bits/stdc++.h>
using namespace std;

struct ele_t {
   int price, value, qty;
};
ele_t dat[503];
int f[6003];

int main() {
   int n, m;
   scanf("%d%d", &m, &n);
   for (int i = 1; i <= n; i++)
      scanf("%d%d", &dat[i].price, &dat[i].value);
   for (int i = 1; i <= n; i++)
      for (int j = m; j >= dat[i].price; j--)
         f[j] = max(f[j], f[j - dat[i].price] + dat[i].value);

   printf("%d", f[m]);
   return 0;
}